给定一个长度为 n 的整数序列 a1 , a2 , … , an。我们称一个二元组(i,j)是完美配对的,当且仅当 i<j 并且 ai−aj=j−i.求完美配对的二元组数目.
对于前 3 个测试点
1≤n≤103
对于后两个测试点
1≤n≤105
所有的测试点都满足
1≤ai≤105
输入格式:
1 | n |
输出格式:
输出完美配对的二元组数目
输入样例:
1 | 5 |
输出样例:
仅有一对二元组(1, 2)满足条件, 因为 3 - 2 = 2 - 1.
1 | 1 |
思路
暴力循环会超时
只要两个元素满足ai−aj=j−i,即ai+i=aj+j,元素数+索引数相等即可配对
开数组标记每个元素的元素数+索引数的和,扫描给定数组,每扫描一个数,寻找前面已扫描过的满足ai+i=aj+j的数量即可
代码
1 |
|